|
Given a prefix-free Turing machine, the universality probability of it is the probability that it remains universal even when every input of it (as a binary string) is prefixed by a random binary string. More formally, it is the probability measure of reals (infinite binary sequences) which have the property that every initial segment of them preserves the universality of the given Turing machine. This notion was introduced by the computer scientist Chris Wallace and was first explicitly discussed in print in an article by Dowe〔 * (and (here ))〕 (and a subsequent article〔 *Dowe, D. L. (2011), "(MML, hybrid Bayesian network graphical models, statistical consistency, invariance and uniqueness" ), Handbook of the Philosophy of Science - (HPS Volume 7) Philosophy of Statistics, P.S. Bandyopadhyay and M.R. Forster (eds.), Elsevier, pp901-982〕). However, relevant discussions also appear in an earlier article by Wallace and Dowe.〔Wallace, C. S. & Dowe, D. L. 1999 ''(Minimum message length and Kolmogorov complexity )'' Computer J. 42, 270–283〕 == Universality probabilities of prefix-free UTMs are non-zero == Although the universality probability of a Universal Turing Machine (UTM) was originally suspected to be zero, relatively simple proofs exist that the supremum of the set of universality probabilities is equal to 1, such as a proof based on random walks〔 *Hernandez-Orallo, J. & Dowe, D. L. (2013), "On Potential Cognitive Abilities in the Machine Kingdom", (Minds and Machines ), Vol. 23, Issue 2, (pp179-210 )〕 and a proof in Barmpalias and Dowe (2012). Once we have one prefix-free UTM with a non-zero universality probability, it immediately follows that all prefix-free UTMs have non-zero universality probability. Further, because the supremum of the set of universality probabilities is 1 and because the set is dense in the interval (1 ), suitable constructions of UTMs (e.g., if ''U'' is a UTM, define a UTM ''U''2 by ''U''2(0''s'') halts for all strings ''s'', U2(1''s'') = ''U''(''s'') for all s) gives that the set of universality probabilities is dense in the open interval (0, 1). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Universality probability」の詳細全文を読む スポンサード リンク
|